

package main.new_2024.month_04;


import main.dataStruct.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @Description: todo 894. 所有可能的真二叉树
 * 给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。
 * 答案中每棵树的每个节点都必须符合 Node.val == 0 。
 * 答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。
 * 真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2024/2/27
 * @Param:
 * @return:
 **/
public class Solution0402 {

    //所有可能的真二叉树
    public List<TreeNode> allPossibleFBT(int n) {
        return process(n);
    }

    public List<TreeNode> process(int n) {
        List<TreeNode> res = new ArrayList<>(); // 我自己的信息
        //n - 1 直接返回
        if (n ==1){
            res.add(new TreeNode(0));
            return res;
        }
        //不是奇数，说明构成不了树
        if (n%2 ==0){
            return res;
        }
        //左边树从1开始，每次要加2个，右边就是n-左边-1
        for (int i =1;i<n;i=i+2){
            List<TreeNode> leftInfo = process(i);
            List<TreeNode> rightInfo = process(n-i-1);
            //遍历构成树
            for (TreeNode l : leftInfo) {
                for (TreeNode r : rightInfo) {
                    TreeNode node = new TreeNode(0, l, r);
                    res.add(node);
                }
            }
        }
        return res;
    }

}

